package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/minimum-distance-between-bst-nodes/description
 *
 * 题型：二叉树的中序遍历
 *
 * ```
 * 783. 二叉搜索树节点最小距离
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * 差值是一个正数，其数值等于两值之差的绝对值。
 *
 * 示例 1：
 * 输入：root = [4,2,6,1,3]
 * 输出：1
 *
 * 示例 2：
 * 输入：root = [1,0,48,null,null,12,49]
 * 输出：1
 *
 * 提示：
 * 树中节点的数目范围是 [2, 100]
 * 0 <= Node.val <= 105
 * ```
 */
class leetcode_783 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n6 = TreeNode(6)
        val root = n4

        n4.left = n2
        n4.right = n6

        n2.left = n1
        n2.right = n3

        val actual = minDiffInBST(root)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n12 = TreeNode(12)
        val n48 = TreeNode(48)
        val n49 = TreeNode(49)
        val root = n1

        n1.left = n0
        n1.right = n48

        n48.left = n12
        n48.right = n49

        val actual = minDiffInBST(root)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }


    fun minDiffInBST(root: TreeNode?): Int {
        /**
        思路：考虑递增方向，使用二叉树的中序遍历（左中右）
        使用pre 节点记录上一个节点，当pre 不为空时，计算pre和current 的差值绝对值，然后取该差值与全局差值的最小值
         */
        if (null == root) {
            return 0
        }
        f(root)
        return min
    }

    var min: Int = Int.MAX_VALUE
    var pre: TreeNode? = null

    fun f(root: TreeNode?) {
        // 1 确认函数参数以及返回值

        // 2 确认终止条件
        if (null == root) {
            return
        }

        // 3 确认递归逻辑：中序遍历
        // 左
        f(root.left)

        // 中
        pre?.let {
            min = Math.min(min, Math.abs(it.`val` - root.`val`))
        }
        pre = root

        // 右
        f(root.right)
    }
}